\( \newcommand{\IN}{\mathbb{N}} \newcommand{\INs}{\mathbb{N}^\ast} \newcommand{\INo}{\mathbb{N}_0} \newcommand{\IZ}{\mathbb{Z}} \newcommand{\IRnn}{\IR_{\geq 0}} \newcommand{\IRsp}{\IR_{\gt 0}} \newcommand{\IR}{\mathbb{R}} \newcommand{\IC}{\mathbb{C}} \newcommand{\A}{\mathcal{A}} \newcommand{\B}{\mathcal{B}} \newcommand{\U}{\mathfrak{U}} \newcommand{\coloneqq}{:=} \newcommand{\coloniff}{:\iff} \newcommand{\Set}[1]{\left\{#1\right\}} \newcommand{\SMid}{\,\middle|\,} \newcommand{\set}[1]{\{#1\}} \newcommand{\smid}{\,|\,} \newcommand{\PSet}[1]{2^{#1}} \newcommand{\supp}{\mathrm{supp}} \newcommand{\dist}[2]{\mathrm{dist}^c_{#1}(#2)} \newcommand{\dists}[2]{{\mathrm{dist}^c_{#1}}'(#2)} \newcommand{\Ind}{{\Large\raise{0pt}{\unicode{x1D7D9}}\,}} \newcommand{\bigO}{\mathcal{O}} \newcommand{\abs}[1]{\left|#1\right|} \newcommand{\norm}[1]{\left\|#1\right\|} \newcommand{\scalar}[2]{\left\langle #1,#2 \right\rangle} \newcommand{\rDeriv}{\partial_+} \newcommand{\lDeriv}{\partial_-} \newcommand{\queue}{q} \newcommand{\Pc}{\mathcal{P}} \newcommand{\Wc}{\mathcal{W}} \newcommand{\diff}{\mathrm{d}} \newcommand{\eps}{\varepsilon} \newcommand{\ql}[1][e]{Q_{#1}} \newcommand{\fvals}[1]{\mathrm{value}(#1)} \newcommand{\fval}[1]{\mathrm{value}(#1)} \newcommand{\ccaps}[1]{\mathrm{capacity}(#1)} \newcommand{\fcosts}[1]{\mathrm{cost}(#1)} \newcommand{\edgesFrom}[1]{\delta^+(#1)} \newcommand{\edgesTo}[1]{\delta^-(#1)} \newcommand{\PathSet}{\mathcal{P}} \newcommand{\CycleSet}{\mathcal{C}} \)

Lecture: Mon, 12:15-13:45 in IM, HS 12

Exercise: Tue, 10:15-11:45 in ITZ, SR 004

Dynamic Network Flows

Lukas Graf
lukas.graf@uni-passau.de

$(x_e) \in \IR^E$ (edge-based) $s$,$t$-flow:

$0 \leq x_e \leq \nu_e$ for all $e \in E$
$\sum_{e \in \edgesTo{v}}x_e = \sum_{e \in \edgesFrom{v}}x_e$ for all $v \in V\setminus\Set{s,t}$
$\mathrm{value}(x)\coloneqq \sum_{e \in \edgesTo{t}}x_e - \sum_{e \in \edgesFrom{t}}x_e \geq 0$

$(x_p) \in \IR^{\PathSet\cup\CycleSet}$ path-cycle-based $s$,$t$-flow:

$0 \leq x_p$ for all $p \in \PathSet\cup\CycleSet$
$\mathrm{value}(x)\coloneqq \sum_{p \in \PathSet}x_p$

Lemma 2.3: $x,y \in \IR^E, \alpha \in \IR, z \coloneqq x+\alpha\cdot y$. Then

$x,y$ satisfy flow cons. at $v$ $\implies$ $z$ satisfies flow cons. at $v$
$x$ $s$,$t$-flow, $y$ satisfies flow cons. at $v \neq s,t$, $\mathrm{value}(x)+\alpha\cdot\mathrm{value}(y)\geq 0$, $0 \leq z \leq \nu$
$\implies$ $z$ $s$,$t$-flow with $\mathrm{value}(z) = \mathrm{value}(x)+\alpha\cdot\mathrm{value}(y)$
$x$ $s$,$t$-flow, $y = \chi_p$ for $p \in \PathSet$, $\alpha\geq -\mathrm{value}(x)$, $x_e+\alpha \in [0,\nu_e]$ f.a. $e \in p$
$\implies$ $z$ $s$,$t$-flow with $\mathrm{value}(z) = \mathrm{value}(x)+\alpha$
$x$ $s$,$t$-flow, $y = \chi_c$ for $c \in \CycleSet$, $x_e+\alpha \in [0,\nu_e]$ f.a. $e \in c$
$\implies$ $z$ $s$,$t$-flow with $\mathrm{value}(z) = \mathrm{value}(x)$

$(x_e)$ maximum $s$,$t$-flow $\coloniff$ $\forall s$,$t$-flows $(y_e)$: $\fvals{y} \leq \fvals{x}$

Extreme Value Theorem: $K$ non-empty, compact, $f: K \to \IR$ continuous
mmmmmmmmmmmmmmmm $\implies$ $\exists x^* \in K: f(x^*) = \sup\Set{f(x) \SMid x \in K}$

bidirected graph $G^\leftrightarrow = (V,E^\leftrightarrow)$ with $E^\leftrightarrow \coloneqq E \,\,\dot{\cup}\,\, \set{e^\leftarrow \coloneqq wv \smid e=vw \in E}$
residual capacity $\nu_e^x \coloneqq \nu_e-x_e$ and $\nu_{e^\leftarrow}^x \coloneqq x_e$
residual graph $G^x = (V,E^x)$ with $E^x \coloneqq \set{e \in E^\leftrightarrow | \nu_e^x \gt 0}$
residual network $N^x = (G^x,s,t,\nu^x)$
augmenting $x$ along $p$ by $\alpha$ gives $(y_e)$ with $y_e \coloneqq \begin{cases}x_e+\alpha, &e \in p \text{ forward edge}\\x_e-\alpha, &e^\leftarrow \in p \text{ backward edge}\\x_e\end{cases}$

Ford-Fulkerson-Algorithm:

Input: $s$,$t$-network $N$
Output: maximum $s$,$t$-flow $x$ in $N$

(1) Start with $x_e \leftarrow 0$ f.a. $e \in E$

(2) While $\exists x$-augmenting $s$,$t$-path in $N^x$ Do

(3) .. compute $\alpha \leftarrow \min\set{\nu^x_e \smid e \in p}$

(4) .. augment $x$ along $p$ by $\alpha$

$A \subseteq V$ $s$,$t$-cut $\coloniff$ $s \in A, t \notin A$
⇝ has capacity $\ccaps{A} \coloneqq \sum_{e \in \edgesFrom{A}}\nu_e$

Lemma 2.14: For any $s$,$t$-flow $x$ and $s$,$t$-cut $A$ we have
$\fvals{x} = \sum_{e \in \edgesFrom{A}}x_e - \sum_{e \in \edgesTo{A}}x_e \leq \ccaps{A}$.

$(x_e)$ min-cost-flow $\coloniff$ $\forall s$,$t$-flows $(y_e)$: $\fvals{y} = \fvals{x} \implies \fcosts{y} \geq \fcosts{x}$

Extreme Value Theorem: $K$ non-empty, compact, $f: K \to \IR$ continuous
mmmmmmmmmmmmmmmm $\implies$ $\exists x_* \in K: f(x_*) = \inf\Set{f(x) \SMid x \in K}$

node-labels $\ell_v \coloneqq \inf\set{\gamma_p \smid p \text{ a } s,v\text{-path}}$

Lemma 2.23: For any $N$ with all nodes reachable from $s$, the following are equivalent:

no cycles of negative cost
reduced costs w.r.t. $\ell$ are non-negative
$\exists \pi \in \IR^V: \gamma^\pi \geq 0$

reduced costs wrt. $\pi \in \IR^V$: $\gamma^\pi_{vw} \coloneqq \gamma_{vw} + \pi_v-\pi_w$

Lemma 2.26: $N^x$ without negative cycles and $p$ an efficient $s$,$t$-path.
mmmm Then, augmenting along $p$ does not create negative cycles.

Lemma 2.27: For any $s$,$t$-flow $x$:
mm $x$ min-cost-flow $\iff$ no negative cycles in $N^x$

Cycle-Cancelling-Algorithm:

Input: $s$,$t$-network $N=(G,s,t,\nu,\gamma)$,
Input: value $v \leq$ min-cut-cap
Output: min-cost-flow $x$ of value $v$ in $N$

(1) Start with any $s$,$t$-flow $x$ of value $v$

(2) While $\exists x$-augmenting cycle $c$ with $\gamma_c \lt 0$ Do

(3) .. augment $x$ along $c$ by $\min\set{\nu^x_e \smid e \in c}$

Successive-Shortest-Path-Algorithm:

Input: $s$,$t$-network $N=(G,s,t,\nu,\gamma)$ without cycles
Input: of negative cost, value $v \leq$ min-cut-cap
Output: min-cost-flow $x$ of value $v$ in $N$

(1) Start with zero flow $x$

(2) While $\fvals{x} \lt v$ Do

(3) .. compute efficient $s$,$t$-path $p$ in $N^x$

(4) .. augment $x$ along $p$ by $\min\set{v-\fvals{x},\min\set{\nu^x_e \smid e \in c}}$

flow dependent edge cost: $\gamma_e: \IRnn \to \IR$
→ path-cost $\gamma_p: \IRnn^E \to \IR, (x_e) \mapsto \sum_{e \in p}\gamma_e(x_e)$

Theorem 2.30: The following are equivalent for a path-based flow $(x_p)$:

$(x_p)$ is Wardrop equilibrium, i.e. $x_p \gt 0 \implies \gamma_p(x) \leq \gamma_q(x)$ f.a. $p,q \in \PathSet$
$(x_p)$ satisfies $\sum_{p \in \PathSet}\gamma_p(x)(y_p-x_p) \geq 0$ f.a. $(y_p)$ with same value as $(x_p)$ “path-based variational inequality”
$(x_p)$ satisfies $\sum_{e \in E}\gamma_e(x_e)(y_e-x_e) \geq 0$ f.a. $(y_p)$ with same value as $(x_p)$ “edge-based variational inequality”
$(x_p)$ is optimal solution to $\min \Phi(y) \coloneqq \sum_{e \in E}\int_0^{y_e}\gamma_e(z)dz$ s.t. $(y_p)$ has same value as $(x_p)$